package com.cat.dynamicPlanning;

import java.util.List;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/maximum-value-of-k-coins-from-piles/description/
 * @create 2025/9/2 16:35
 * @since JDK17
 */

public class Solution50 {
    public int maxValueOfCoins(List<List<Integer>> piles, int k) {
        int n = piles.size();
        int[] dp = new int[k + 1];
        for (int i = 0; i < n; i++) {
            List<Integer> list = piles.get(i);
            int[] prefix = new int[list.size() + 1];
            int end = Math.min(k, list.size());
            for (int j = 0; j < end; j++) {
                prefix[j + 1] = prefix[j] + list.get(j);
            }
            // 对于第i个数组拿l个硬币
            for (int j = k; j >= 0; j--) {
                for (int l = 1; l <= Math.min(end, j); l++) {
                    dp[j] = Math.max(dp[j], dp[j - k] + prefix[k]);
                }
            }
        }
        return dp[k];
    }
}
